The term “Turing machine” refers to a theoretical computing device that performs computations in a manner first postulated by Alan Turing. Most modern electrical computers are instantiations of Turing machines. In general, a Turing machine may be understood as a device that has the ability to read symbols stored on, and to write symbols onto, an endless tape. The tape may be initialized to contain one or more symbols. Furthermore, the Turing machine has a “state” which may change over time. Often such states are described using simple labels, such as numbers (e.g., states 1, 2, and 3) or letters (e.g., states A, B, and C), but the particular labels that are used to identify states is not important.
The Turing machine includes a read/write head which, at any particular time, is positioned over a particular position on the tape, referred to as the “current position.” The Turing machine reads the symbol currently stored at the current position on the tape (referred to herein as the “current input”) and, based on that symbol and the Turing machine's current state, determines what action to perform next. Such actions include writing a specified symbol at the current position on the tape, the direction in which to move the head (forward or backward), and modifying the state of the Turing machine. The Turing machine may be associated with rules which specify the action(s) to take when the Turing machine reads a particular symbol while the Turing machine is in a particular state. Each such rule may specify any one or more of the types of actions just described. Examples of such rules include: “If symbol 1 is read while in state A, then write the symbol 2 at the current position and move one position forward,” “If symbol 2 is read while in state A, then transition to state B,” and “If symbol 1 is read while in state B, then write the symbol 3 at the current position, transition to state A, and move one position backward.”
After performing the action(s) specified by a rule that is applicable to the current state and the current input, the Turing machine again reads the symbol currently stored at the current position on the tape, and the process above repeats.
The set of rules associated with a particular Turing machine may themselves be encoded in symbols on the Turing machine's tape. In this case, the Turing machine may read the rule-containing symbols and then effectively apply the rules embodied in those symbols to the subsequent symbols on the tape. A Turing machine which is able to apply encoded rules in this way is referred to as a “universal Turing machine” because it may be made to mimic any other specific Turing machine by providing it with the correct set of rule-encoding symbols. The set of rule-encoding symbols is also referred to as a computer program.
A Turing machine may be deterministic or non-deterministic. In a deterministic Turing machine, the set of rules that is associated with the Turing machine unambiguously specify the action(s) to be performed for each state-input combination. For example, a deterministic Turing machine specifies may specify the following: “If symbol 2 is read while in state A, then transition to state B,” and specify no other action to be taken if symbol 2 is read while in state A. In contrast, the rules associated with a non-deterministic Turing machine (NTM) may specify two or more alternate actions to be performed for a state-input combination. For example, a NTM may specify both of the following rules: “If symbol 2 is read while in state A, then transition to state B” and “If symbol 2 is read while in state A, then transition to state C.”
As the description above implies, in a deterministic Turing machine, the combination of the current state and current input uniquely (i.e., unambiguously) specify the symbol (if any) to be written at the current position, the direction (if any) to move the head, and the new state of the Turing machine (which may be the same as the current state). As the description above further implies, in a nondeterministic Turing machine, the combination of the current state and current input do not necessarily uniquely specify the symbol (if any) to be written at the current position, the direction (if any) to move the head, and the new state of the Turing machine (which may be the same as the current state). A nondeterministic Turing machine is nondeterministic, therefore, because the combination of the current state and the current input do not necessarily determine the symbol to be written by the Turing machine at the current position, the Turing machine's next state, and the Turing machine's next position.
A non-deterministic Turing machine may be thought of as a knowledge reasoning machine which works in a manner that is similar to the human brain. In each situation, a non-deterministic Turing machine may make many choices in parallel to move towards the solution of a problem. In contrast, a deterministic Turing machine is a transition function machine; that is, in any given situation, a deterministic Turing machine makes exactly one choice, and does not have the ability to pursue other choices in parallel. Therefore, the most significant difference between a deterministic Turing machine and a non-deterministic Turing machine is that the former cannot perform processing in parallel, while the latter can perform processing in parallel.
There is no known method for constructing an implementation of a non-deterministic Turing machine. Furthermore, it is not known whether a nondeterministic Turing machine can be constructed from a deterministic Turing machine. If a nondeterministic Turing machine could be constructed from a deterministic Turing machine, then it would be possible to solve problems in computing with significantly greater efficiency than is now possible.